import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class ArrayHeapMinPQ<T> {
    private class priorityNode implements Comparable{
        T item;
        double priority;
        //priorityNode包含了储存的item和item对应的优先级，只有这样，我们才能修改对应item的优先级
        //普通的优先队列，优先级是隐含的，包含在元素之内，通过元素与元素之间的比较才能确定优先级
        //索引优先队列，优先级在元素之外，可以改变特定元素的优先级
        public priorityNode(T item, double priority) {
            this.item = item;
            this.priority = priority;
        }

        @Override
        public int compareTo(Object o) {
            if (o == null) return -1;
            if (o.getClass() != this.getClass()) return -1;
            return Double.compare(this.priority, ((priorityNode) o).priority);
        }
    }

    private List<priorityNode> pq = new ArrayList<>();
    private Map<T, Integer> itemToIndex = new HashMap<>();

    public ArrayHeapMinPQ() {
        pq.add(null);
    }
    /* Inserts an item with the given priority value. */
    void add(T item, double priority){
        pq.add(new priorityNode(item, priority));
        itemToIndex.put(item, pq.size() - 1);
        swim(pq.size() - 1);
    }

    public boolean isEmpty(){
        return size() == 0;
    }
    private void exch(int i, int j) {
        priorityNode t = pq.get(i);
        itemToIndex.put(pq.get(i).item, j);
        itemToIndex.put(pq.get(j).item, i);
        pq.set(i, pq.get(j));
        pq.set(j, t);
    }

    private boolean less(int i, int j) {
        return pq.get(i).compareTo(pq.get(j)) < 0;
    }
    private void swim(int k) {
        if (k / 2 >= 1 && less(k, k / 2)) {
            exch(k / 2, k);
            swim(k / 2);
        }
    }

    private void sink(int index) {
        int j = 2 * index;
        if (j > pq.size()-1) return;
        if (j + 1 <= pq.size()-1 && less(j + 1, j)) j++;
        if (less(index, j)) return;
        exch(index, j);
        sink(j);
    }
    /* Returns true if the PQ contains the given item. */
    boolean contains(T item){
        return itemToIndex.containsKey(item);
    }
    /* Returns the minimum item. */
    T getSmallest(){
        return pq.get(1).item;
    }
    /* Removes and returns the minimum item. */
    T removeSmallest(){
        T t = pq.get(1).item;
        exch(1, pq.size() - 1);
        itemToIndex.remove(pq.get(pq.size() - 1).item);
        pq.remove(pq.size() - 1);
        sink(1);
        return t;
    }
    /* Changes the priority of the given item. Behavior undefined if the item doesn't exist. */

    /**
     * 改变对应item的priority，如果不包含这个item，就将它添加进优先队列
     * @param item
     * @param priority
     */
    void changePriority(T item, double priority){
        int index = itemToIndex.get(item);
        double curPriority = pq.get(index).priority;
        pq.get(index).priority = priority;
        if (priority > curPriority) sink(index);
        else swim(index);
    }
    /* Returns the number of items in the PQ. */
    int size(){
        return pq.size() - 1;
    }
}
